home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / bbsutil / hsrc_117.zip / HEADLZSS.C < prev    next >
Text File  |  1990-10-22  |  21KB  |  798 lines
  1. /**************************************************************
  2.     lzhuf.c
  3.     written by Haruyasu Yoshizaki 1988/11/20
  4.     some minor changes 1989/04/06
  5.     comments translated by Haruhiko Okumura 1989/04/07
  6.     This stuff is pretty much the original article, but
  7.     M. Kimes hacked on it in June of 1990
  8.     Screwed with everything to work with XBBS msg bases
  9. **************************************************************/
  10.  
  11. #include "msgg.h"
  12. #include "twindow.h"
  13. #include "keys.h"
  14. #include "headedit.h"
  15.  
  16. static int  pascal Encode (void);
  17. static int  pascal Decode (void);
  18. static int  pascal GetBit (void);
  19. static int  pascal GetByte (void);
  20. static void pascal InitTree (void);            /* initialize trees */
  21. static void pascal InsertNode (int r);           /* insert to tree */
  22. static void pascal DeleteNode (int p);         /* remove from tree */
  23. static void pascal StartHuff (void);           /* init tree */
  24. static void pascal EncodeChar (unsigned c);
  25. static void pascal EncodePosition (unsigned c);
  26. static void pascal EncodeEnd (void);
  27. static int  pascal DecodeChar (void);
  28. static int  pascal DecodePosition (void);
  29. static void pascal Putcode (int l, unsigned c);
  30. static void pascal Lupdate (int c);
  31. static int  pascal alloc_stuff (void);
  32. static void pascal free_stuff (void);
  33.  
  34. /********** LZSS compression **********/
  35.  
  36. #define N           4096        /* buffer size */
  37. #define F           60             /* lookahead buffer size */
  38. #define THRESHOLD   2
  39. #define NIL         N              /* leaf of tree */
  40.  
  41. typedef unsigned char uchar;
  42.  
  43. static unsigned getbuf;
  44. static uchar getlen;
  45. static unsigned putbuf;
  46. static uchar putlen;
  47. static unsigned int bytesdone, bytestodo;
  48. static int           match_position, match_length;
  49. static unsigned char *text_buf;
  50. static int           *lson;
  51. static int           *rson;
  52. static int           *dad;
  53. static char *inbuf;
  54. static char *outbuf;
  55.  
  56. /************ Miscellaneous *************/
  57.  
  58. #define EXIT_FAILURE 1
  59. #define EXIT_SUCCESS 0
  60.  
  61. extern unsigned int textsize, codesize;
  62. extern struct _xmsg   msg;
  63.  
  64.  
  65. int pascal Encode ()  { /* compression */
  66.  
  67.     int  i, c, len, r, s, last_match_length;
  68.     unsigned int printcount=0;
  69.  
  70.     if(!alloc_stuff()) {
  71.         printf("\n\x1b[1CCouldn't allocate encode buffers!\n");
  72.         return 0;
  73.     }
  74.     codesize = bytesdone = textsize = 0;
  75.     printf("\x1b[1CCompressing...\n");
  76.     StartHuff();
  77.     InitTree();
  78.     s = 0;
  79.     r = N - F;
  80.     for (i = s; i < r; i++) {
  81.         text_buf[i]=0x20;
  82.     }
  83.     for (len = 0; len < F; len++) {
  84.         c=(int) *inbuf;
  85.         if(!c) break;
  86.         inbuf++;
  87.         bytesdone++;
  88.         if(bytesdone>bytestodo) break;
  89.         text_buf[r+len]=c;
  90.     }
  91.     textsize = len;
  92.     for (i = 1; i <= F; i++) InsertNode(r - i);
  93.     InsertNode(r);
  94.     do {
  95.         if (match_length > len)
  96.             match_length = len;
  97.         if (match_length <= THRESHOLD) {
  98.             match_length = 1;
  99.             EncodeChar(text_buf[r]);
  100.         } else {
  101.             EncodeChar(255 - THRESHOLD + match_length);
  102.             EncodePosition(match_position);
  103.         }
  104.         last_match_length = match_length;
  105.         for (i = 0; i < last_match_length; i++) {
  106.             c=(int)*inbuf;
  107.             if(!c) break;
  108.             inbuf++;
  109.             bytesdone++;
  110.             if(bytesdone>bytestodo) break;
  111.             DeleteNode(s);
  112.             text_buf[s] = c;
  113.             if (s < F - 1)
  114.                 text_buf[s + N] = c;
  115.             s = (s + 1) & (N - 1);
  116.             r = (r + 1) & (N - 1);
  117.             InsertNode(r);
  118.         }
  119.         if ((textsize += i) > printcount) {
  120.             printf("\r\x1b[1C%u",textsize);
  121.             printcount += 1024;
  122.         }
  123.         while (i++ < last_match_length) {
  124.             DeleteNode(s);
  125.             s = (s + 1) & (N - 1);
  126.             r = (r + 1) & (N - 1);
  127.             if (--len) InsertNode(r);
  128.         }
  129.     } while (len > 0);
  130. EndIt:
  131.     EncodeEnd();
  132.     printf("\r\x1b[1C%u bytes -> %u bytes",textsize,codesize);
  133.     free_stuff();
  134.     return 1;
  135. }
  136.  
  137.  
  138. int pascal Decode ()  { /* recover */
  139.  
  140.     int  i, j, k, r, c;
  141.     unsigned int count;
  142.     unsigned int printcount=0;
  143.  
  144.     codesize=0;
  145.     if (textsize<1024) {
  146.         printf("\n\x1b[1CTextsize=%u!\n",textsize);
  147.         return 0;
  148.     }
  149.  
  150.     if(!alloc_stuff()) {
  151.         printf("\n\x1b[1CCouldn't allocate decode buffers!\n");
  152.         return 0;
  153.     }
  154.  
  155.     printf("\x1b[13;2H");
  156.     StartHuff();
  157.     for (i = 0; i < N - F; i++) text_buf[i]=0x20;
  158.     r = N - F;
  159.     for (count = 0; count < textsize; ) {
  160.         c = DecodeChar();
  161.         if (c < 256) {
  162.             *outbuf=(char)c;
  163.             outbuf++;
  164.             text_buf[r++] = c;
  165.             r &= (N - 1);
  166.             count++;
  167.         }
  168.         else {
  169.             i = (r - DecodePosition() - 1) & (N - 1);
  170.             j = c - 255 + THRESHOLD;
  171.             for (k = 0; k < j; k++) {
  172.                 c = text_buf[(i + k) & (N - 1)];
  173.                 *outbuf=(char)c;
  174.                 outbuf++;
  175.                 text_buf[r++] = c;
  176.                 r &= (N - 1);
  177.                 count++;
  178.             }
  179.         }
  180.         if (count > printcount) {
  181.             printf("\r\x1b[1C%u  ", count);
  182.             printcount += 1023;
  183.         }
  184.     }
  185.     free_stuff();
  186.     printf("\x1b[13;2H                            ");
  187. /*
  188. if(count>textsize) {
  189.     printf("\x1b[1COVERFLOW: count=%u  textsize=%u\n",count,textsize);
  190.     pause();
  191. }
  192. */
  193.     return 1;
  194. }
  195.  
  196.  
  197. static void pascal InitTree (void) { /* initialize trees */
  198.  
  199.     int  i;
  200.  
  201.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;    /* root */
  202.     for (i = 0; i < N; i++) dad[i] = NIL;                /* node */
  203. }
  204.  
  205.  
  206. static void pascal InsertNode (int r) { /* insert to tree */
  207.  
  208.     int  i, p, cmp;
  209.     unsigned char  *key;
  210.     unsigned c;
  211.  
  212.     cmp = 1;
  213.     key = &text_buf[r];
  214.     p = N + 1 + key[0];
  215.     rson[r] = lson[r] = NIL;
  216.     match_length = 0;
  217.     for ( ; ; ) {
  218.         if (cmp >= 0) {
  219.             if (rson[p] != NIL)
  220.                 p = rson[p];
  221.             else {
  222.                 rson[p] = r;
  223.                 dad[r] = p;
  224.                 return;
  225.             }
  226.         } else {
  227.             if (lson[p] != NIL)
  228.                 p = lson[p];
  229.             else {
  230.                 lson[p] = r;
  231.                 dad[r] = p;
  232.                 return;
  233.             }
  234.         }
  235.         for (i = 1; i < F; i++)
  236.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  237.                 break;
  238.         if (i > THRESHOLD) {
  239.             if (i > match_length) {
  240.                 match_position = ((r - p) & (N - 1)) - 1;
  241.                 if ((match_length = i) >= F)
  242.                     break;
  243.             }
  244.             if (i == match_length) {
  245.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  246.                     match_position = c;
  247.                 }
  248.             }
  249.         }
  250.     }
  251.     dad[r] = dad[p];
  252.     lson[r] = lson[p];
  253.     rson[r] = rson[p];
  254.     dad[lson[p]] = r;
  255.     dad[rson[p]] = r;
  256.     if (rson[dad[p]] == p)
  257.         rson[dad[p]] = r;
  258.     else
  259.         lson[dad[p]] = r;
  260.     dad[p] = NIL; /* remove p */
  261. }
  262.  
  263. static void pascal DeleteNode (int p)  /* remove from tree */
  264. {
  265.     int  q;
  266.  
  267.     if (dad[p] == NIL)
  268.         return;         /* not registered */
  269.     if (rson[p] == NIL)
  270.         q = lson[p];
  271.     else
  272.     if (lson[p] == NIL)
  273.         q = rson[p];
  274.     else {
  275.         q = lson[p];
  276.         if (rson[q] != NIL) {
  277.             do {
  278.                 q = rson[q];
  279.             } while (rson[q] != NIL);
  280.             rson[dad[q]] = lson[q];
  281.             dad[lson[q]] = dad[q];
  282.             lson[q] = lson[p];
  283.             dad[lson[p]] = q;
  284.         }
  285.         rson[q] = rson[p];
  286.         dad[rson[p]] = q;
  287.     }
  288.     dad[q] = dad[p];
  289.     if (rson[dad[p]] == p)
  290.         rson[dad[p]] = q;
  291.     else
  292.         lson[dad[p]] = q;
  293.     dad[p] = NIL;
  294. }
  295.  
  296. /* Huffman coding */
  297.  
  298. #define N_CHAR   (256 - THRESHOLD + F)
  299.                  /* kinds of characters (character code = 0..N_CHAR-1) */
  300. #define T        (N_CHAR * 2 - 1)    /* size of table */
  301. #define R        (T - 1)         /* position of root */
  302. #define MAX_FREQ 0x8000      /* updates tree when the */
  303.                  /* root frequency comes to this value. */
  304.  
  305.  
  306. /* table for encoding and decoding the upper 6 bits of position */
  307.  
  308. /* for encoding */
  309. uchar p_len[64] = {
  310.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  311.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  312.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  313.     0x07, 0